/*
 *     Copyright (c) 2021. cc01cc. All rights reserved.
 *
 *     This file is part of this file.
 *
 *     This file is free software: you can redistribute it and/or modify
 *     it under the terms of the GNU Affero General Public License as published
 *     by the Free Software Foundation, either version 3 of the License, or
 *     (at your option) any later version.
 *
 *     This file is distributed in the hope that it will be useful,
 *     but WITHOUT ANY WARRANTY; without even the implied warranty of
 *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *     GNU Affero General Public License for more details.
 *
 *     You should have received a copy of the GNU Affero General Public License
 *     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#include <stdio.h>
#include <stdlib.h>

struct Peanut
{
//    the prefix 'i' means the location or index
    int i_row;
    int i_column;
//    The prefix 'n' means the amount of something.
//    e.g. the amount of peanuts in one plant;
    int n_peanut;
//    The total time go to a plant.
//    Include the picking.
    int n_time_go;
//    Generally speaking, the range is from small to large
//    e.g. n_go_time
//    But in order to distinguish the categories of 'time' and 'peanut'
//    put them in the order of 'time' followed by 'go' or 'back'.
    int n_time_back;
};

typedef struct Peanut Peanut;

int storeData(int row, int column, Peanut* p_peanut);
void sortLargeToSmall(Peanut* p_peanut, int limit);
void peanutInitial(Peanut* p_peanut);
int countPeanutPicked(Peanut* p_peanut, int limit, int n_plant_have_peanut);
int main()
{
    int row, column;
    int n_time_limit;
    int n_plant_have_peanut;
    int n_peanut_picked;
    Peanut peanut[1000];


    scanf("%d%d%d", &row, &column, &n_time_limit);
//    if no plants have peanuts return 0.
    n_plant_have_peanut = storeData(row, column, peanut);
    if(n_plant_have_peanut==0) return 0;
    sortLargeToSmall(peanut, n_plant_have_peanut);
    peanutInitial(peanut);
    n_peanut_picked = countPeanutPicked(peanut, n_time_limit, n_plant_have_peanut);
    printf("The number of peanut is %d.", n_peanut_picked);
}

/*
*   @return the number of plants contain peanuts.
*   @function the value of i_row i_column n_time_back in p_peanut
*/
int storeData(int row, int column, Peanut* p_peanut)
{
    int i,j,data;
    int i_peanut = 0;
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < column; j++)
        {
            scanf("%d", &data);
            if(data!=0)
            {
                p_peanut[i_peanut].i_row = i+1;
                p_peanut[i_peanut].i_column = j+1;
                p_peanut[i_peanut].n_time_back = i+1;
                p_peanut[i_peanut].n_peanut = data;
//                printf(
//                       "p_peanut's index, i_row, i_column, n_time_back, n_peanut is %d, %d, %d, %d, %d\n",
//                       i_peanut, p_peanut[i_peanut].i_row,
//                       p_peanut[i_peanut].i_column,
//                       p_peanut[i_peanut].n_time_back,
//                       p_peanut[i_peanut].n_peanut
//                       );
                i_peanut++;
            }
        }
    }
    return i_peanut;
}

//    Use Insertion Sort.
void sortLargeToSmall(Peanut* p_peanut, int limit)
{
    int i, j,x;

    Peanut p_tmp;
//    for(i = 0; i < limit; i++)
//    {
//        printf("p_peanut index is %d, n_peanut is %d, n_time_back is %d\n", i, p_peanut[i].n_peanut,p_peanut[i].n_time_back);
//    }
//    printf("\n");
    for(i = 1; i < limit; i++)
    {
        p_tmp = p_peanut[i];
        for(j = i; j > 0 && p_peanut[j - 1].n_peanut < p_tmp.n_peanut; j--)
        {
            p_peanut[j] = p_peanut[j - 1];
        }
//        for(x = 0; x < limit; x++)
//        {
//            printf("p_peanut index is %d, n_peanut is %d\n", x, p_peanut[x].n_peanut);
//        }
//        printf("\n");
        p_peanut[j] = p_tmp;
    }
//    for(i = 0; i < limit; i++)
//    {
//        printf("p_peanut index is %d, n_peanut is %d, n_time_back is %d\n", i, p_peanut[i].n_peanut,p_peanut[i].n_time_back);
//    }
}

/*
*   !make sure p_peanut[0] has value.
*   @function define the p_peanut[0]'s n_time_go
*/
void peanutInitial(Peanut* p_peanut)
{
    p_peanut[0].n_time_go = p_peanut[0].i_row+1;
}

int countPeanutPicked(Peanut* p_peanut, int limit, int n_plant_have_peanut)
{
    int i = 0;
    int n_peanut_picked = 0;
    while(i<n_plant_have_peanut&&p_peanut[i].n_time_go+p_peanut[i].n_time_back<=limit)
    {
//        printf("p_peanut[i].n_peanut is %d\n", p_peanut[i].n_peanut);
        n_peanut_picked += p_peanut[i].n_peanut;
        i++;
        p_peanut[i].n_time_go = abs(p_peanut[i].i_column-p_peanut[i-1].i_column)
        + abs(p_peanut[i].i_row-p_peanut[i-1].i_row)
        + p_peanut[i-1].n_time_go + 1;
//        printf("p_peanut[%d].n_time_go is %d; n_time_back is %d\n", i, p_peanut[i].n_time_go, p_peanut[i].n_time_back);
//        printf("p_peanut index is %d, n_time_go is %d, n_time_back is %d\n", i, p_peanut[i].n_time_go, p_peanut[i].n_time_back);
//        printf("n_peanut_picked is %d\n", n_peanut_picked);
    }
//    if(p_peanut[i].n_time_go+p_peanut[i].n_time_back<limit)
//    {
//        return p_peanut[i].n_time_go+p_peanut[i].n_time_back;
//    }else
//    {
//        return p_peanut[i-1].n_time_go+p_peanut[i-1].n_time_back;
//    }
//    printf("n_peanut_picked is %d\n", n_peanut_picked);
    return n_peanut_picked;
}
